package master;


import java.util.*;

/**
 * @author chenyw
 * @date 2022/9/3 15:45
 */
public class M187findRepeatedDnaSequences {
    static final int L = 10;
    Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
        put('A', 0);
        put('C', 1);
        put('G', 2);
        put('T', 3);
    }};
    public List<String> findRepeatedDnaSequences(String s) {
        List<String> list = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        if (s.length() <= L) {
            return list;
        }
        int x = 0;
        for (int i = 0; i < L -1; i++) {
            x = (x << 2) | bin.get(s.charAt(i));
        }
        for (int i = 0; i <= s.length() - L; i++) {
            int a = bin.get(s.charAt(i));
            x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << 20) - 1);
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) == 2) {
                list.add(s.substring(i, i + L));
            }

        }
        return list;
    }


/*    //时间复杂度NL, hashcode
    public static List<String> findRepeatedDnaSequences(String s) {

        List<String> list = new ArrayList<>();
        if (s.length() <= 10) {
            return list;
        }
        Map<String, Integer> map = new HashMap<>();

//        Set<String> set = new HashSet<>();
//        set.add(s.substring(0, 10));
        map.put(s.substring(0, 10), 0);
        for (int i = 11; i <= s.length(); i++) {

            String str = s.substring(i - 10, i);
            if (map.containsKey(str)) {
                if (map.get(str) == 0) {
                    map.put(str, 1);
                    list.add(str);
                }
            } else {
                map.put(str, 0);
            }
        }
        return list;
    }*/
}
